High Efficiency Video Coding (HEVC) is a video compression standard that is the successor of the H.264/AVC video compression standard. HEVC achieves significant improvements for both intra-picture (intra) coding and inter-picture (inter) coding over H.264/AVC. For the case of intra coding, the main differences between HEVC and H.264/AVC are the larger number of directional modes (35 prediction modes instead of 9) and the larger number of block sizes (from 4×4 to 32×32 instead of 4×4 to 16×16). FIG. 1 illustrates the 33 prediction angles used in HEVC. Each prediction angle corresponds to a directional mode or intra mode.
HEVC also supports two additional modes: planar and DC. The angles are defined so that the displacement between the angles is smaller close to horizontal and vertical directions and coarser towards the diagonal directions, as can be seen in FIG. 1.
A typical HEVC encoder performs an intra prediction search to determine the intra mode to be used by the current block. After the best intra mode is selected, the prediction signal for the current block is generated using the pixels of previously processed blocks of the same picture. A residual signal is then formed by taking the difference between the original block and the prediction block, hence spatial redundancies are extracted to reduce the amount of data that needs to be transmitted to represent the picture.
The intra mode of the current block is encoded into a bit stream utilizing a three-entry most probable mode (MPM) list. H.264/AVC uses a single motion vector predictor (unless direct mode is used) and a single MPM. HEVC uses multiple candidate predictors or MPMs together with an index or flag for signaling the selected predictor or MPM, respectively. This list is generated using a process defined in the HEVC standard that utilizes the left and above modes and includes three unique intra modes. If the desired mode is in the list, the index to the list is sent, otherwise the mode is sent explicitly.
Referring to FIG. 2, intra prediction is the process of predicting block M from previously processed blocks A, B, C, D and E. As shown in FIG. 3, adjacent pixels and angular offsets (intra modes) from the previously processed blocks are used to construct the reference data that is used to predict M. The basic assumption for intra prediction is that the texture of any block is similar to the texture of adjacent blocks and therefore can be predicted from the adjacent blocks.
In the encoder previous block data needs to be available when performing the full prediction of block M, otherwise there will be a mismatch between the encoder and the decoder, as the decoder uses the reconstructed data from those blocks to reconstruct block M.
In addition to determining the best mode for each block, an HEVC encoder needs to determine the partitioning of the blocks. In HEVC, a Coding Tree Unit (CTU) can be split into smaller blocks in a quad-tree manner. For example, a 64×64 CTU can be first split into 4 32×32 blocks and each 32×32 block can be split further.
FIG. 4 illustrates an example splitting of a block, where a 64×64 block is first split into four 32×32 blocks (including displayed blocks A and M). The top-right and the bottom left 32×32 blocks are then split into four 16×16 blocks (e.g., 16×16 blocks B, C, D, E). Furthermore, one of the bottom left 16×16 blocks is split into four 8×8 blocks (i.e., G, H, I, J).
The samples used for prediction determine how the blocks are split. For example, as shown in FIG. 4, the pixels belonging to block H use samples from the neighboring blocks: A, D, E, G, I, K. However, if the blocks G,H,I,J were not split but were a single block of size 16×16, pixels from blocks, A,D,E,F,K would be used for prediction.
Because the distance between the prediction pixel and original pixel is always smaller when smaller block sizes are used, it is generally the case that using smaller blocks yields better predictions. However, it is generally more expensive to code smaller blocks due to the increased overhead associated with transmitting information for the increased numbers of blocks.
For this reason, an efficient algorithm to determine the block partitioning for HEVC is very important. More particularly, it is important to provide a good tradeoff between the accuracy of the prediction and the number of bits used.